# -*- coding: utf-8 -*-

"""剑指 Offer II 051. 节点之和最大的路径
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。

示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：
树中节点数目范围是 [1, 3 * 10^4]
-1000 <= Node.val <= 1000"""


# Definition for a binary tree node.


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """这道题翻译成大白话就是，选取一个节点，计算其左右路径和的最大值，再比较获得所有节点的最大值。
    
    此题应该计算后缀和，利用栈来表示前进顺序，同时需要保留后退节点的情形，所以每获取一个子节点，往栈里要添加两个子节点，一个表示退出时，一个表示进入时
    
    注意，本题目节点数范围超过1000，不能用递归，可能造成栈溢出问题。
    此时为了模仿递归时的进入退出位置，内置 enter/exit 两种状态来实现，(1, TreeNode) 即将进入该节点，(0, TreeNode) 即将退出该节点。
    enter: 进入节点后，往栈里加节点
    exist: 退出节点前，利用当前节点，左路径表，右路径表计算最大当前最大路径；退出节点后前缀和消解，判断返回到父节点的左右子树路径哪个表
    
    由上，需要标识3种行为，进入节点（0），退出节点-父节点左子树节点路径表（-1），退出节点-父节点右子树节点路径表（1）；
    
    前面对于每个节点左右子树路径采用哈希表来存储，每返回一个节点都进行最大值运算，虽然结果是正确的，但是在提交后，有个树节点很多，导致超时；
    继续改进，每一步求得最值后，还要计算出该子节点退出后能为父节点 leftpath 或 rightpath 返回的最值，用 exist_path 表示，这样每步比较的的时候就将集合求最值变为值求最值，
    看题解，这也叫动态规划？"""
    def maxPathSum(self, root: TreeNode) -> int:
        max_path_sum = -1000

        guard = TreeNode(0, right=root)
        guard.lpath = None
        guard.rpath = None

        root.parent = guard
        root.lpath = None
        root.rpath = None

        stack = []
        stack.append((1, root))
        stack.append((0, root))
        while True:
            try:
                sign, node = stack.pop()
                if sign == 0:
                    if node.right:
                        node.right.parent = node
                        node.right.lpath = None
                        node.right.rpath = None
                        stack.append((1, node.right))
                        stack.append((0, node.right))
                    if node.left:
                        node.left.parent = node
                        node.left.lpath = None
                        node.left.rpath = None
                        stack.append((-1, node.left))
                        stack.append((0, node.left))
                    continue

                val, left_path, right_path = node.val, node.lpath, node.rpath
                if left_path is not None and right_path is not None:
                    max_path_sum = max(max_path_sum, val, left_path, right_path, val+left_path, val+right_path, val+left_path+right_path)
                    exit_path = max(val, val+left_path, val+right_path)
                elif left_path is not None:
                    max_path_sum = max(max_path_sum, val, left_path, val+left_path)
                    exit_path = max(val, val+left_path)
                elif right_path:
                    max_path_sum = max(max_path_sum, val, right_path, val+right_path)
                    exit_path = max(val, val+right_path)
                else:
                    max_path_sum = max(max_path_sum, val)
                    exit_path = val

                if sign < 0:
                    node.parent.lpath = exit_path
                elif sign > 0:
                    node.parent.rpath = exit_path
        
            except IndexError:
                break
        
        return max_path_sum
    
    def maxPathSumRecursion(self, root):
        """其实递归只是一种更方便理解的实现方式，任务在内部，上下级关系也在内部
        每退出一个节点有两个任务：
            1.计算以当前节点为顶点，左右子节点路径组合的最大值，与旧最大值比较
            2.返回以当前节点为顶点的最大路径，用于父节点计算
        
        这次提交，效率要比循环要快很多，猜测循环主要在为 TreeNode 节点添加 parent, lpath, rpath三个属性，
        每次进入节点时，都涉及三个属性的创建，
        每次退出节点时，都涉及三个属性的访问，赋值。"""
        max_path_sum = -1000
        def max_path(node):
            nonlocal max_path_sum
            lpath, rpath = None, None
            if node.left:
                lpath = max_path(node.left)
            if node.right:
                rpath = max_path(node.right)

            if lpath is not None and rpath is not None:
                max_path_sum = max(max_path_sum, node.val, lpath, rpath, node.val+lpath, node.val+rpath, node.val+lpath+rpath)
                exit_path = max(node.val, node.val+lpath, node.val+rpath)
            elif lpath is not None:
                max_path_sum = max(max_path_sum, node.val, lpath, node.val+lpath)
                exit_path = max(node.val, node.val+lpath)
            elif rpath is not None:
                max_path_sum = max(max_path_sum, node.val, rpath, node.val+rpath)
                exit_path = max(node.val, node.val+rpath)
            else:
                max_path_sum = max(max_path_sum, node.val)
                exit_path = node.val
            return exit_path
        max_path(root)
        return max_path_sum


if __name__ == '__main__':
    so = Solution()
    root = TreeNode(1, TreeNode(2), TreeNode(3))
    # root = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
    # root = TreeNode(1, right=TreeNode(2, right=TreeNode(3, right=TreeNode(4, right=TreeNode(5)))))
    max_path_sum = so.maxPathSumRecursion(root)
    print(max_path_sum)

